#include "main/utils.h"
#include "lib/list.h"
using namespace std;

class Solution {
  public:
    ListNode* reverseList(ListNode* head) {
      if (!head) {
        return nullptr;
      }

      ListNode* pre = head;
      ListNode* cur = pre->next;
      ListNode* back = nullptr;
      head->next = nullptr;
      while (cur) {
        back = cur->next;
        cur->next = pre;
        pre = cur;
        cur = back;
      }
      return pre;
    }

    ListNode* reverseList1(ListNode* head) {
      if (!head || !head->next) {
        return head;
      }
      auto new_head = reverseList1(head->next);
      head->next->next = head;
      head->next = nullptr;
      return new_head;
    }
};

int main() {
  vector<int> node_vals = {1, 2, 3, 4, 5};
  ListNode* phead = CreateList(node_vals);
  Solution su;
  auto output = su.reverseList(phead);
  PrintList(output);

  ListNode* phead1 = CreateList(node_vals);
  auto output1 = su.reverseList1(phead1);
  PrintList(output1);

  return 0;
}
